import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Sort {
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if (tmp<array[j]){
                    array[j+1]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap= array.length;
        while (gap>1){
            gap/=2;
            shell(array,gap);
        }
    }
    public static void shell(int []array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0 ; j=j-gap) {
                if (tmp<array[j]){
                    array[j+gap]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    public static void swap(int[]array,int x,int y){
        int tmp=array[x];
        array[x]=array[y];
        array[y]=tmp;
    }
    public static void selectSort(int[]array){
        for (int i = 0; i < array.length; i++) {
            int minIndex= i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j]< array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void selectSort2(int[]array){
        for (int i = 0; i < array.length/2; i++) {
            int minIndex= i;
            int maxIndex= i;
            for (int j = i+1; j < array.length-i; j++) {
                if (array[j]< array[minIndex]){
                    minIndex=j;
                }
                if (array[j]> array[maxIndex]){
                    maxIndex=j;
                }
            }
            swap(array,minIndex,i);
            if (maxIndex==0){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,array.length-1-i);
        }
    }
    public static void siftDown(int []array,int parent,int end){
        int child=parent*2+1;
        while (child<end+1){
            if (child+1<=end){
                if (array[child+1]>array[child]){
                    child++;
                }
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }

        }


    }
    public static void createBigHeap(int[]array){
        int child=array.length-1;
        int parent= (child-1)/2;
        while (parent>=0){
            siftDown(array,parent,array.length-1);
            parent--;
        }
    }

    public static void heapSort(int []array){
        //调整为大根堆
        createBigHeap(array);
        int end= array.length-1;
        while (end>0){
            swap(array,0,end);
            end--;
            siftDown(array,0,end);

        }
    }
    public static int  partition2(int []array,int left,int right){
        int tmp=array[left];
        while (left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
       array[left]=tmp;
        return left;
    }
    public static int  partition(int []array,int left,int right){
        int tmp=array[left];
        int i=left;
        while (left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            while (left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }
    private static int midThreeNum(int[]array,int left,int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[left] > array[mid]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    public static void insertSort(int[] array,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if (tmp<array[j]){
                    array[j+1]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static void quick(int []array,int start,int end){
        if (start>=end) {
            return;
        }
        if((end-start)<10){
            insertSort(array,start,end);
            return;
        }
        int mid=midThreeNum(array,start,end);
        swap(array,mid,start);

        int par=partition(array,start,end);
        quick(array,start,par-1);
        quick(array,par+1,end);
    }
    public static void quickSort(int[]array){
        quick(array,0,array.length-1);
    }
    public static void quickSortNor(int []array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int par=partition(array,left,right);
        if (left+1<par){
            stack.push(left);
            stack.push(par-1);
        }
        if (right-1>par){
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            par=partition(array,left,right);
            if (left+1<par){
                stack.push(left);
                stack.push(par-1);
            }
            if (right-1>par){
                stack.push(par+1);
                stack.push(right);
            }
        }

    }
    //基数排序
    public static void radixSort(int []array){
        //1，创立19个队列，下标为0-18的队列分别对应的-9到9的数字
        Queue<Integer>[] queues=new Queue[19];
        //2，选出来最大值位数
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i < array.length; i++) {
            if (maxVal<array[i]){
                maxVal=array[i];
            }
            if (minVal>array[i]){
                minVal=array[i];
            }
        }
        if (minVal<0&&maxVal<-minVal){
            maxVal=-minVal;
        }
        //3，遍历最大数位次
        int ret=1;
        while (maxVal>0){
            //4，遍历数组的每一位，根据该值对应位次的数字，将该值储存到对应的下标中
            for (int i = 0; i < array.length; i++) {
                int tmp;
                if(array[i]<=0){
                    tmp=9-((-array[i]/ret)%10);
                }else {
                    tmp=9+((array[i]/ret)%10);
                }
                if (queues[tmp]==null){
                    queues[tmp]=new LinkedList<>();
                }
                queues[tmp].offer(array[i]);
            }
            //5，将将列队中的数据以顺序的方式取出，重新放回数组中
            int j=0;
            for (int i = 0; i < queues.length; i++) {
                while (queues[i]!=null&&!queues[i].isEmpty()){
                    array[j]=queues[i].poll();
                    j++;
                }
            }
            //6，最大的位数减一
            maxVal/=10;
            ret*=10;
        }
    }
    public static void countSort(int[]array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i < array.length; i++) {
            if (maxVal<array[i]){
                maxVal=array[i];
            }
            if (minVal>array[i]){
                minVal=array[i];
            }
        }
        int[]count=new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        int j=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0) {
                array[j] = i + minVal;
                j++;
                count[i]--;
            }
        }
    }
    private static void merge(int []array,int left,int mid,int right){
        int b1=left;
        int e1=mid;
        int b2=mid+1;
        int e2=right;
        int index=0;
        int[] tmp=new int[right-left+1];
        while (b1<=e1&&b2<=e2){
            if (array[b1]<=array[b2]){
                tmp[index]=array[b1];
                index++;
                b1++;
            } else {
                tmp[index]=array[b2];
                index++;
                b2++;
            }
        }
        while (b1<=e1){
            tmp[index++]=array[b1++];
        }
        while (b2<=e2){
            tmp[index++]=array[b2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i+left]=tmp[i];
        }
    }
    public static void mergeSortFun(int[]array,int left,int right){
        if (left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortFun(array,left,mid);
        mergeSortFun(array,mid+1,right);
        merge(array,left,mid,right);
    }
    public static void mergeSortNor(int[]array){
        int gap=1;
        while (gap<array.length) {
            for (int i = 0; i < array.length; i = i + 2 * gap) {
                int left = i;
                int mid = i + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }
    public static void mergeSort(int [] array){
        mergeSortFun(array,0,array.length-1);

    }



}
class Test{
    public static void main(String[] args) {
        int []array={20,10,6,6,4,-1,8,2,7,1,19,-3,0};
        /*Sort.insertSort(array);*/
        /*Sort.shellSort(array);*/
       /* Sort.selectSort2(array);*/
       /* Sort.heapSort(array);*/
        Sort.mergeSort(array);
        System.out.println(Arrays.toString(array));

    }
}
